#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/7/1 15:09
# @USER    : Shengji He
# @File    : MaximumLengthofRepeatedSubarray.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        """
        Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

        Example 1:
            Input:
                A: [1,2,3,2,1]

                B: [3,2,1,4,7]
            Output: 3

            Explanation:
                The repeated subarray with maximum length is [3, 2, 1].
        Note:
            - 1 <= len(A), len(B) <= 1000
            - 0 <= A[i], B[i] < 100

        :param A:
        :param B:
        :return:
        """
        dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
        ans = 0
        for i in range(len(A) - 1, -1, -1):
            for j in range(len(B) - 1, -1, -1):
                dp[i][j] = dp[i + 1][j + 1] + 1 if A[i] == B[j] else 0
                ans = max(dp[i][j], ans)

        return ans


if __name__ == '__main__':
    S = Solution()
    A = [1, 2, 3, 2, 1]
    B = [3, 2, 1, 4, 7]
    print(S.findLength(A, B))
    print('done')
